class A {

    /**
     * @param A:      an integer sorted array
     * @param target: an integer to be inserted
     * @return: An integer
     */
    public int searchInsert(int[] A, int target) {
        // write your code here


        return searchInsert(A, 0, A.length - 1, target);

    }

    public int searchInsert(int[] A, int l, int r, int target) {
        // write your code here

        if (l == r || l == r - 1) {
            return l;
        }

        int mid = (l + r) >>> 2;
//        System.out.println(mid);
        if (A[mid] > target) {
            return searchInsert(A, l, mid - 1, target);
        } else {
            return searchInsert(A, mid + 1, r, target);
        }
    }

    public static void main(String[] args) {
        System.out.println(new A().searchInsert(new int[]{1, 3, 5, 6}, 5));
    }
}

